#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 10
typedef int KeyType;
typedef struct
{
    KeyType key;
} RedType;
typedef struct
{
    RedType r[MAXSIZE + 1];
    int length;
} SqList;

int partition(SqList &L, int low, int high)
{
    KeyType pivotkey;
    RedType k;
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;
    while (low < high)
    { //再一次快速排序中只要low的值比hight小，我们就应该去移动，
        //因为当前这次排序还没有完成
        while (low < high && L.r[high].key >= pivotkey)
            --high;           //表示只有当前指针没有重合并且当前右边hight指向的值大于key时，才会向左移动hight
        L.r[low] = L.r[high]; //将比key小的值赋到low
        while (low < high && L.r[low].key <= pivotkey)
            ++low;
        L.r[high] = L.r[low];
    }                  //将比key大的值赋到hight上
    L.r[low] = L.r[0]; //找到了所属的位置，并且将我们选定的值key赋到这个位置上去
    return low;
}

void quicksort(SqList &L, int low, int high) //  //快速排序算法的实质就是当前分为两半，
//分别给这两半进行快速排序，直到low==hight的时候
{
    int pivotpos;
    if (low < high)
    { //先对整体进行一次快速排序，将其分成两半
        pivotpos = partition(L, low, high);
        quicksort(L, low, pivotpos - 1); // 然后分别对该位置左边的部分在进行快速排序，位置右边的部分进行快速排序
        quicksort(L, pivotpos + 1, high);
    }
}
void quicksort(SqList &L)
{
    quicksort(L, 1, L.length);
}
void display(SqList L)
{
    int i;
    for (i = 1; i <= L.length; i++)
        printf("%6d", L.r[i].key);
    printf("\n");
}
int main()
{
    int i;
    SqList L;
    printf("please input length of creat a list:");
    scanf("%d", &L.length);
    printf("\nplease input a group of key to creat a list:\n ");
    for (i = 1; i <= L.length; i++)
        scanf("%d", &L.r[i].key);
    quicksort(L, 1, L.length);
    printf("output result of sort:\n");
    display(L);
    return 1;
}
